/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.replica.replicaisland;

import java.util.Comparator;

public class QuickSorter<Type> extends Sorter<Type> {
	public void sort(Type[] array, int count, Comparator<Type> comparator) {
		quicksort(array, 0, count - 1, comparator);
	}

	// Quicksort implementation based on the one here:
	// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
	/*************************************************************************
	 * 
	 * Generate N random real numbers between 0 and 1 and quicksort them.
	 * 
	 * On average, this quicksort algorithm runs in time proportional to N log
	 * N, independent of the input distribution. The algorithm uses Sedgewick's
	 * partitioning method which stops on equal keys. This protects against
	 * cases that make many textbook implementations, even randomized ones, go
	 * quadratic (e.g., all keys are the same).
	 * 
	 *************************************************************************/

	/***********************************************************************
	 * Quicksort code from Sedgewick 7.1, 7.2.
	 ***********************************************************************/

	// quicksort a[left] to a[right]
	public void quicksort(Type[] a, int left, int right,
			Comparator<Type> comparator) {
		if (right <= left)
			return;
		int i = partition(a, left, right, comparator);
		quicksort(a, left, i - 1, comparator);
		quicksort(a, i + 1, right, comparator);
	}

	// partition a[left] to a[right], assumes left < right
	private int partition(Type[] a, int left, int right,
			Comparator<Type> comparator) {
		int i = left - 1;
		int j = right;
		while (true) {
			while (comparator.compare(a[++i], a[right]) < 0) { // find item on
																// left to swap
			} // a[right] acts as sentinel
			while (comparator.compare(a[right], a[--j]) < 0) { // find item on
																// right to swap
				if (j == left) {
					break; // don't go out-of-bounds
				}
			}
			if (i >= j) {
				break; // check if pointers cross
			}
			Type swap = a[i]; // swap two elements into place
			a[i] = a[j];
			a[j] = swap;
		}
		Type swap = a[i]; // swap with partition element
		a[i] = a[right];
		a[right] = swap;
		return i;
	}
}
